package top;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;

/**
 *
 * 快速排序的优化，快速选择（又引入随机索引，将两个while变成一个for）
 * 快速选择：可以一次比安利后确定一个元素在哪个位置
 *
 * @author chenyw
 * @date 2022/7/18 21:55
 */
public class Top215findKthLargest {
    Random random = new Random();
    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, 0, nums.length - 1, nums.length - k);
    }

    //快排入口
    private int quickSelect(int[] nums, int l, int r, int k) {
        int q = randomPartition(nums, l, r);
        if (q == k) {
            return nums[q];
        } else {
            return q > k ? quickSelect(nums, l, q - 1, k) : quickSelect(nums, q + 1, r, k);
        }
    }

    //使用随机索引替换平常的mid
    private int randomPartition(int[] nums, int l, int r) {
        int i = random.nextInt(r - l + 1) + l;
        swap(nums, i, r);
        return partitions(nums, l, r);
    }

    private void swap(int[] nums, int i, int r) {
        int tmp = nums[i];
        nums[i] = nums[r];
        nums[r] = tmp;
    }

    //排序的关键代码，
    private int partitions(int[] nums, int l, int r) {
        int tmp = nums[r];
        int i = l - 1;
        //j用来表示遍历的个数，没什么用；
        for (int j = l; j < r; j++) {
            //最关键的一行代码， 可以把小于tmp的元素放到i的左面，大于它的放在i的右边
            if (nums[j] <= tmp) {
                swap(nums, ++i, j);
            }
        }
        swap(nums, i + 1, r);
        return i + 1;
    }

}
